package graph.impl;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdOut;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class StringGraphDFP {
	private Map<String,Boolean> visited = null;
	private StringGraph graph = null;
	private Map<String,String> previousEdgeMap = null;
	
	public StringGraphDFP(StringGraph graph, String sourceVertex) {
		this.graph = graph;
		visited = new HashMap<String, Boolean>();
		previousEdgeMap = new HashMap<String,String>();
		dfs(sourceVertex);
	}
	
	public void dfs(String sourceVertex){
		visited.put(sourceVertex, Boolean.TRUE);
		Set<String> edges = graph.getEdges(sourceVertex);
		for(String edge : edges){
			if(!visited.containsKey(edge)){
				previousEdgeMap.put(edge, sourceVertex);
				dfs(edge);
			}
		}
	}
	public boolean hasPathTo(String destinationVertex){
		return visited.get(destinationVertex);
	}
	public Stack<String> pathTo(String source, String dest){
		Stack<String> path = new Stack<String>();		
		if(!source.equals(dest)){
			String currentNode = previousEdgeMap.get(dest);
			path.push(dest);
			while(!currentNode.equals(source)){
				path.push(currentNode);
				currentNode = previousEdgeMap.get(currentNode);
			}
			path.push(currentNode);
		}	else	{
			path.push(source);
		}
		
		return path;
	}
	public static void main(String[] args) {

		In in = new In(args[0]);
		StringGraph stringGraph = new StringGraph(in);
		String source = args[1].trim();
		StringGraphDFP dfs = new StringGraphDFP(stringGraph,source);
		
		Set<String> vertices = dfs.graph.getVertices();
		
		for(String dest : vertices){
			if(dfs.hasPathTo(dest)){
				StdOut.print(source  + " to " + dest +":: ");
				Stack<String> paths = dfs.pathTo(source, dest);
				while(!paths.isEmpty()){
					String path = paths.pop();
					if(path.equals(source))	{
						StdOut.print(path);
					}	else	{
						StdOut.print("-" + path);
					}					
					
				}
			}
			StdOut.println();
		}

	}

}
